import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;

import java.util.*;


/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-02-14
 * Time: 14:42
 */
class TreeNode{
    char val;
    TreeNode left;
    TreeNode right;
    public TreeNode(char val){
        this.val=val;
    }
}
public class Main {
    public class TreeNode1 {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode1(int x) { val = x; }
  }


    public static class ListNode {
        int val;
 ListNode next;
 ListNode(int x) { val = x; }
 }

    public static void main(String[] args) {
        System.out.println("hello world！");
    }


    public static void main12(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int s=sc.nextInt();
        int[][] arr1=new int[n][2];
        for(int i=0;i<n;i++){
            for(int j=0;j<2;j++){
                arr1[i][j]=sc.nextInt();
            }
        }

        //大于等于175并且大于等于90的一定会被录取
        //一共有k个批次，只要是大于等于175的，就会有至多k个被录取
        int count=0;
        for(int i=0;i<n;i++){
            int a1=arr1[i][0];
            int a2=arr1[i][1];
            if(a1>=175 && a2>=90){
                count++;
                arr1[i][0]=0;
                arr1[i][1]=0;
            }
        }

        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<n;i++){
            if(arr1[i][0]>=175){
                if(map.containsKey(arr1[i][0])){
                    //包含
                    map.put(arr1[i][0],map.get(arr1[i][0])+1);
                }else{
                    map.put(arr1[i][0],1);
                }
            }
        }

        //遍历map
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            int h=entry.getValue();
            if(h<=k){
                count+=h;
            }else{
                count+=k;
            }
 }

        System.out.println(count);
    }



    public static void main10(String[] args){
        Scanner sc=new Scanner(System.in);
        String str1=sc.next();
        String str2=sc.next();
        String s1="";
        String s2="";
        for (int i = 1; i < str1.length(); i++) {
            char ch1=str1.charAt(i);
            char ch2=str1.charAt(i-1);
            int ret1=ch1-48;
            int ret2=ch2-48;
            if (ret1 % 2 == ret2 % 2) {
                s1 += ""+Math.max(ret1, ret2);
            }
        }

        for (int i = 1; i < str2.length(); i++) {
            char ch1=str2.charAt(i);
            char ch2=str2.charAt(i-1);
            int ret1=ch1-48;
            int ret2=ch2-48;
            if (ret1 % 2 == ret2 % 2) {
                s2 += ""+Math.max(ret1, ret2);
            }
        }

        if(s1.equals(s2)==true){
            System.out.println(s1);
        }else{
            System.out.println(s1);
            System.out.println(s2);
        }
    }


    public static void main9(String[] args){
        Scanner sc=new Scanner(System.in);
        int[] arr=new int[6];
        for(int i=0;i<6;i++){
            arr[i]=sc.nextInt();
        }
        int n=sc.nextInt();
        int[][] arr2=new int[6][5];
        for(int i=0;i<6;i++){
            int ret=arr[i];
            int tmp=1;
            for(int j=0;j<5;j++){
                if(tmp!=ret){
                    arr2[i][j]=tmp;
                }else{
                    arr2[i][j]=++tmp;
                }
                tmp++;
            }
        }

        int m=5-n;
        System.out.println(arr2[0][m]+" "+arr2[1][m]+" "+arr2[2][m]+" "+arr2[3][m]+" "+arr2[4][m]+" "+arr2[5][m]);
    }





    public static void main8(String[] args) {
        //模拟醉汉行走问题，每走一步用随机方法生成步长和方向，每一步可用一个矢量来表示，
        //将这些矢量累加起来可以计算出醉汉最后走出的距离和方向，通过模拟实验，评估其走路的效率。
        //Random ran=new Random();
        int time=0;
        double x=0;
        double y=0;
        while(time!=10){
            double bu=Math.random()*100;
            double fang=Math.random()*361;
            double sin=Math.sin(2*Math.PI*fang/360);
            double cos=Math.cos(2*Math.PI*fang/360);

            //当步长和方向被确定以后，按照方向来判断接下来走的步是属于正方向还是负方向
            //如果方向是在0 - 90 是x是正，y也是正
            //如果方向在90 - 180 就是x是负，y是正
            //如果方向在180 - 270 就是x是负，y也是负
            //如果方向在270 - 360 就是x是正，y是负
            if(fang<=90 && fang>=0){
                x=x+cos*bu;
                y=y+sin*bu;
            }else if(fang>=90 && fang<=180){
                x=x-cos*bu;
                y=y+sin*bu;
            }else if(fang>=180 && fang<=270){
                x=x-cos*bu;
                y=y-sin*bu;
            }else if(fang>=270 && fang<=360){
                x=x+cos*bu;
                y=y-sin*bu;
            }
            double count=Math.sqrt(x*x+y*y);
            fang=Math.atan2(y,x);

            System.out.println("方向是："+fang+"弧度   距离原点的距离是："+count);
            time++;
        }

    }

    public static void main7(String[] args) {
        int i=1;
        System.out.println((++i)+(++i));
    }




    public static void main6(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        for(int i=0;i<m;i++){
            String str=sc.next();
            //right的个数也代表了这个满二叉树叶子节点的个数
            //按照某个规律，得到这个代码，每次回答了一个问题以后，就会减少一半的结点个数
            int right=(int)Math.pow(2,n);//Math.pow(2,n);
            int left=0;
            for(int j=0;j<n-1;j++){
                char ch=str.charAt(j);
                if(ch=='y'){
                    right=(left+right)/2;
                }else{
                    left=(left+right)/2;
                }
            }
            if(str.charAt(n-1)=='y'){
                System.out.println(left+1);
            }else{
                System.out.println(right);
            }
        }
    }


    public static void main2(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        double[] arr=new double[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextDouble();
            if(arr[i]<m){
                System.out.println("On Sale! "+arr[i]);
            }
        }
    }
    public static void main4(String[] args){
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        int h=sc.nextInt();

        //使用顺序表

        ArrayList<Integer> array=new ArrayList<>();
        //当前数和它的后一个数
        int t1=m;
        int t2=n;
        array.add(m);
        array.add(n);
        int i=0;
        while(array.size()<h){
            t1=array.get(i);
            t2=array.get(i+1);
            i++;
            int ret=t1*t2;
            if(ret>10){
                Stack<Integer> stack=new Stack<>();
                while(ret!=0){
                    //得到ret的每一位
                    //放到栈里面，试试
                    stack.add(ret%10);
                    ret=ret/10;
                }
                while(!stack.isEmpty()){
                    array.add(stack.pop());
                }
            }else{
                array.add(ret);
            }
        }

        for(int j=0;j<h;j++){

            if(j==h-1){
                System.out.println(array.get(j));
            }else{
                System.out.println(array.get(j)+" ");
            }
        }
    }




    public static void main5(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int s=sc.nextInt();
        StringBuilder[] str=new StringBuilder[n];
        //String[] str=new String[n];
        for(int i=0;i<n;i++){
            String ret1=sc.next();
            str[i]=new StringBuilder(ret1);
            //输入不行
        }
        int ret=sc.nextInt();
        Stack<Character> stack=new Stack<>();
        while(ret!=-1){
            if(ret==0){
                if(!stack.isEmpty()){
                    //打印此时stack中的栈顶的数据
                    System.out.println(stack.pop());
                }
            }else{
                if(!stack.isEmpty() && stack.size()==s){
                    System.out.print(stack.pop());
                }
                //str[ret-1]
                if(str[ret-1].length()!=0){

                    stack.add(str[ret-1].charAt(0));
                    str[ret-1].deleteCharAt(0);
                }
            }

            ret=sc.nextInt();
        }
    }






    public static void main3(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        //int[] arr=new int[n];
        HashMap<Integer,Integer> map=new HashMap<>();
        int m=0;
        for(int i=0;i<n;i++){

            m=sc.nextInt();
            if(map.containsKey(m)){
                map.put(m,map.get(m)+1);
            }else{
                map.put(m,1);
            }
        }
        int small=m;
        int hall=0;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            int ret=entry.getKey();
            if(small>ret){
                small=ret;
            }
            if(hall<ret){
                hall=ret;
            }
        }
        if(!map.isEmpty()){
            int s=map.get(small);
            int h=map.get(hall);
            System.out.println(small+" "+s);
            System.out.println(hall+" "+h);
        }

    }






    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        //借助栈来求解，利用相交链表的思想
        //难点：把从根节点开始到p或者q结点的这个路径找到并存到相应的栈内的操作
        Stack<TreeNode> stack1=new Stack<>();
        Stack<TreeNode> stack2=new Stack<>();
        boolean b1=func(root,p,stack1);
        boolean b2=func(root,q,stack2);
        int len1=stack1.size();
        int len2=stack2.size();
        if(len1>len2){
            int ret=len1-len2;
            while(ret!=0){
                stack1.pop();
                ret--;
            }
        }else{
            int ret=len2-len1;
            while(ret!=0){
                stack2.pop();
                ret--;
            }
        }
        //到这里的时候，2个栈内的数据个数就一样了
        //开始遍历看是否相等
        while(!stack1.isEmpty() && !stack2.isEmpty()){
            if(stack1.peek()==stack2.peek()){
                return stack1.peek();
            }else{
                stack1.pop();
                stack2.pop();
            }
        }
        //栈为空了都没找到，就返回null
        return null;
    }
    public boolean func(TreeNode root, TreeNode p,Stack<TreeNode> stack){
        //难点：把从根节点开始到p或者q结点的这个路径找到并存到相应的栈内的操作
        if(root!=null){
            stack.add(root);
        }
        if(root==null){
            return false;
        }
        if(root==p){
            return true;
        }
        //递归
        boolean left=func(root.left,p,stack);
        boolean right=func(root.right,p,stack);
        if(left==false && right==false){
            stack.pop();
            return false;
        }
        return true;
    }





    public static void main1(String[] args) {
        String[] words = {"cat","bt","hat","tree"};
        String chars = "atach";
        int count=countCharacters(words,chars);
        System.out.println(count);
    }
    public static int countCharacters(String[] words, String chars) {
        //在拼写一个单词的时候，只能使用一次字母表中的字符
        //仅包含小写的英文字母
        //每次字母表中的内容只能使用一次
        int len=words.length;
        int count=0;
        for(int i=0;i<len;i++){
            HashMap<Character,Integer> map=new HashMap<>();
            for(int m=0;m<chars.length();m++){
                char ch= chars.charAt(m);
                if(map.containsKey(ch)){
                    map.put(ch,map.get(ch)+1);
                }else{
                    map.put(ch,1);
                }
            }

            int j=0;
            for(j=0;j<words[i].length();j++){
                char ch1=words[i].charAt(j);
                if(map.containsKey(ch1) && map.get(ch1)!=0){
                    map.put(ch1,map.get(ch1)-1);
                }else if(!map.containsKey(ch1) || map.get(ch1)==0){
                    break;
                }
            }
            if(j==words[i].length()){
                count+=j;
            }
        }
        return count;
    }




    public static void main11(String[] args) {
        ListNode a1=new ListNode(1);
        ListNode a2=new ListNode(2);
        ListNode a3=new ListNode(3);
        ListNode a4=new ListNode(3);
        ListNode a5=new ListNode(4);
        ListNode a6=new ListNode(4);
        ListNode a7=new ListNode(5);
        a1.next=a2;
        a2.next=a3;
        a3.next=a4;
        a4.next=a5;
        a5.next=a6;
        a6.next=a7;
        ListNode a=deleteDuplication(a1);
        System.out.println("===========");

    }

    //{1,2,3,3,4,4,5}
    public static ListNode deleteDuplication(ListNode pHead) {
        // 已排序的链表，返回这个链表的不重复的节点
        if(pHead==null){
            return null;
        }
        ListNode cur=pHead.next;
        ListNode prev=pHead;
        ListNode head=null;
        ListNode last=null;
        //先处理一下头节点的比较
        if(pHead.next!=null){
            if(pHead.val!=pHead.next.val){
                ListNode node=new ListNode(pHead.val);
                if(head==null){
                    head=node;
                    last=node;
                }else{
                    last.next=node;
                }
            }
        }else{
            return pHead;
        }
        while(cur!=null && cur.next!=null){
            //就是：让每一个结点和它存在的前面和后面来进行比较
            //然后创建新的结点放到新的链表里面
            if(cur.val!=prev.val && cur.val!=cur.next.val){
                ListNode node=new ListNode(cur.val);
                if(head==null){
                    head=node;
                    last=node;
                }else{
                    last.next=node;
                }
            }
            prev=cur;
            cur=cur.next;
        }
        //最后处理一下尾结点的比较
        if(cur!=null){
            if(cur.val!=prev.val){
                ListNode node=new ListNode(cur.val);
                if(head==null){
                    head=node;
                    last=node;
                }else{
                    last.next=node;
                }
            }
        }
        if(last!=null){
            last.next=null;
        }
        return head;
    }




    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案
        //在nums2中找到nums1中相同的数字
        int[] arr=new int[nums1.length];
        int e=0;
        for(int i=0;i<nums1.length;i++){
            // nums1[i]
            int j;
            for(j=0;j<nums2.length;j++){
                if(nums1[i]==nums2[j]){
                    int ret=nums2[j];
                    while(j<nums2.length){
                        if(nums2[j]>ret){
                            arr[e]=nums2[j];
                            e++;
                            break;
                        }
                        j++;
                    }
                    if(j==nums2.length){
                        arr[e]=-1;
                        e++;
                    }

                }
            }

        }
        return arr;
    }




    public static int lastStoneWeight(int[] stones) {
        int len=stones.length;
        while(len>1){
            Arrays.sort(stones,0,len);
            int a1=stones[len-1];
            int a2=stones[len-2];
            if(a1==a2){
                len-=2;
            }else{
                stones[len-2]=Math.abs(a1-a2);
                len-=1;
            }
        }
        if(len==1){
            return stones[0];
        }
        return 0;
    }



    public boolean CheckPermutation(String s1, String s2) {
        //把它们变成字符串数组，然后把每个数组排好序，然后一一比较
        if(s1.length()!=s2.length()){
            return false;
        }
        char[] arr1=s1.toCharArray();
        char[] arr2=s2.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        for(int i=0;i<s1.length();i++){
            if(arr1[i]!=arr2[i]){
                return false;
            }
        }
        return true;
    }



    public int dayOfYear(String date) {
        //每个月的天数是不一样的，并且还要区分是不是闰年
        //首先把每个月的天数变成一个数组，然后注意区分是不是闰年
        //然后去计算是今年的第几天
        int[] arr={31,28,31,30,31,30,31,31,30,31,30,31};
        int count=0;
        //把这个字符串变成一个字符串数组，以-来分割的那种
        String[] str=date.split("-");
        int year=Integer.parseInt(str[0]);
        int month=Integer.parseInt(str[1]);
        int day=Integer.parseInt(str[2]);
        if(year%4==0 && year%100!=0 || year%400==0){
            //是闰年
            for(int i=0;i<month-1;i++){
                if(i==1){
                    //第二月时
                    count+=29;
                }else{
                    count+=arr[i];
                }
            }
            count+=day;
        }else{
            //不是闰年
            for(int i=0;i<month-1;i++){
                count+=arr[i];
            }
            count+=day;
        }
        return count;
    }



    public ListNode removeDuplicateNodes(ListNode head) {
        //set可以去重
        ListNode cur=head;
        ListNode newhead=null;
        ListNode last=null;
        HashSet<Integer> set=new HashSet<>();
        while(cur!=null){
            if(set.add(cur.val)){
                if(newhead==null){
                    newhead=cur;
                    last=cur;
                }else{
                    last.next=cur;
                    last=cur;
                }
            }
            cur=cur.next;
        }
        last.next=null;
        return newhead;
    }




    public static boolean isUgly(int n) {
        //求出n的所有的因数，然后看它的所有的质因数是否是 2，3，或者5,如果它还有其他的质因数那么就返回false
        //规定1是一个丑数
        if(n==1){
            return true;
        }
        HashSet<Integer> set=new HashSet<>();
        if(n==0){
            return false;
        }

        //如果是一个负数
        if(n<0){
            //n=n*(-1);
            int ret=n/(-2);
            for(int i=2;i<=ret;i++){
                if(n%i==0 && i%2!=0){
                    set.add(i);
                }
            }
        }

        //如果是正数
        if(n>0){
            for(int i=2;i<=n/2;i++){
                if(n%i==0 && i%2!=0){
                    set.add(i);
                }
            }
        }
        set.remove(2);
        set.remove(3);
        set.remove(5);
        if(set.isEmpty()){
            return true;
        }
        return false;
    }



    public static boolean isHappy(int n){
        int ret=n;
        HashSet<Integer> set=new HashSet<>();
        while(ret!=1){
            ret=func(ret);
            if(set.contains(ret)){
                //ret在set中
                return false;
            }else{
                //ret不在set中
                set.add(ret);
            }
        }
        return true;
    }
    public static int func(int n){
        //得到一个数的每一位，并且把每一位的值都平方然后相加
        int count=0;
        while(n!=0){
            int ret=n%10;
            n=n/10;
            count+=(ret*ret);
        }
        return count;
    }



    public String truncateSentence(String s, int k) {
        String[] str=s.split(" ");
        String ret="";
        for(int i=0;i<k;i++){
            ret=ret+str[i];
            if(i!=k-1){
                ret=ret+" ";
            }
        }
        return ret;
    }

    public static int sqrt (int x) {
        //这个题就是说，要返回x的平方根
        //并且是向下取整的，是int类型的
        if(x==0){
            return 0;
        }
        if(x==1){
            return 1;
        }
        int left=1;
        int right=x;
        int mid=(left+right)/2;
        while(left<=right){
            mid=(left+right)/2;
            double ret=mid*mid;
            if(ret>x){
                right=mid-1;
            }else if(ret<x){
                if((mid+1)*(mid+1)>x){
                    return mid;
                }else{
                    left=mid+1;
                }

            }else if(ret==x){
                return mid;
            }
        }
        return left-1;
    }

}
